//         https://www.nowcoder.com/practice/cb33f5653a064b2eaf1fe30ba18f5977?tpId=295&fromPut=pc_wzcpa_labuladong_sf





class Solution
{
    int arr[110] = { 0 };
    int dp[110][110] = { 0 };

public:
    int getCoins(vector<int>& coins)
    {
        int n = coins.size();
        arr[0] = arr[n + 1] = 1;
        for (int i = 1; i <= n; i++)
            arr[i] = coins[i - 1];

        for (int i = n; i >= 1; i--)
            for (int j = i; j <= n; j++)
                for (int k = i; k <= j; k++)
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);

        return dp[1][n];
    }
};